package 算法.其他算法;

import java.util.ArrayList;
import java.util.HashMap;

public class JZ57和为S的两个数字 {
    //哈希表
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        HashMap<Integer,Integer> map = new HashMap<>();
        ArrayList<Integer> res= new ArrayList<Integer>();
        if(array.length<=1)
            return res;
        for(int i=0;i<array.length;i++){
            map.put(array[i],i);
            if(map.containsKey(sum-array[i])){
                res.add(array[i]);
                res.add(sum-array[i]);
                return res;
            }
        }
        return  res;
    }

    //双指针
    public ArrayList<Integer> FindNumbersWithSum2(int [] array, int sum) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //左右双指针
        int left = 0, right = array.length - 1;
        //对撞双指针
        while(left < right){
            //相加等于sum，找到目标
            if(array[left] + array[right] == sum){
                res.add(array[left]);
                res.add(array[right]);
                break;
            }else if(array[left]+array[right]>sum){
                //和太大，缩小右边
                right--;
            }else{
                //和太小，缩小左边
                left++;
            }
        }
        return  res;
    }
}
